package com.tim.test.leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author
 * @Title:
 * @Package
 * @date 2023/6/6 22:27
 * @Description:
 */
public class Answer2 {
    public static void main(String[] args) {
        Answer2 answer = new Answer2();
        Object r=null;

//        r = answer.maxArea(new int[]{1,8,6,2,5,4,8,3,7});
//        r = answer.removeDuplicates(new int[]{1,1});
//        r = answer.searchInsert(new int[]{1,3,5,6}, 2);
//        r = answer.maxProfit(new int[]{7,1,5,3,6,4});
//        answer.removeKdigits("1432219", 3);
//        System.out.println(JSON.toJSONString(r));
        r  = answer.move(5, 7, 2);
        System.out.println(r);
    }

    /**   
     * 11
     *  面积s=(i-j)*min(h[i], h[j])
     *  双指针。
     */       
    public int maxArea(int[] height) {
        int length = height.length;
        if(length<2){
            return 0;
        }
        int i=0, j=length-1, s=0;
        do{
            s = Math.max(s, Math.min(height[i], height[j])*(j-i));
            if(height[i]<height[j]){
                i++;
            }else{
                j--;
            }
        }while (i<j);
        return s;
    }

    /**   
     * 26
     *  遍历；有相同时，继续判定相同内容长度，一次性移动
     */       
    public int removeDuplicates(int[] nums) {
        if(nums.length<2){
            return nums.length;
        }
        int step = 0;
        int totalSize = 0;
        for (int i = 1; i < nums.length-totalSize; i++) {
            while(i < nums.length-totalSize && nums[i]==nums[i-1]){
                step++;
                i++;
            }
            if(step!=0){
                for (int j = i; j < nums.length-totalSize; j++) {
                    nums[j-step] = nums[j];// 前移
                }
                totalSize += step;
                i = i-step;
                step=0;
            }
        }
        return nums.length-totalSize;
    }

    /**   
     * 35
     */       
    public int searchInsert(int[] nums, int target) {
        if(nums.length==0){
            return 0;
        }if(nums.length==1){
            return nums[0]>=target ? 0 : 1;
        }
        int left = 0;
        int right = nums.length-1;
        if(nums[left]<target && target<nums[right]){
            do{
                int middle = (left+right)/2;
                if(nums[middle]>=target){
                    right = middle;
                }else{
                    left = middle;
                }
            }while (right>left+3);
            for (int i = left; i <= right; i++) {
                if(nums[i]>=target){
                    return i;
                }
            }
        }else{
            return nums[left]>=target ? 0
                    : nums[right]==target ? nums.length-1 : nums.length;
        }

        return 0;
    }

    /**
     * 704
     */
    public int search(int[] nums, int target) {
        if(nums.length==0){
            return -1;
        }if(nums.length==1){
            return nums[0]==target ? 0 : -1;
        }
        int left = 0;
        int right = nums.length-1;
        if(nums[left]<target && target<nums[right]){
            do{
                int middle = (left+right)/2;
                if(nums[middle]>=target){
                    right = middle;
                }else{
                    left = middle;
                }
            }while (right>left+3);
            for (int i = left; i <= right; i++) {
                if(nums[i]==target){
                    return i;
                }
            }
        }else{
            return nums[left]==target ? 0
                    : nums[right]==target ? nums.length-1 : -1;
        }

        return -1;
    }

    /**
     * 144
     *  递归。从根节点开始，先左后右，排除空值；每个节点都如此操作
     *  考虑root==null的情况
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        result = getTreeList(root, result);

        return result;
    }

    private List<Integer> getTreeList(TreeNode root, List<Integer> result) {
        if(root ==null){
            return result;
        }
        result.add(root.val);
        TreeNode left = root.left;
        if(left!=null){
            getTreeList(left, result);
        }
        TreeNode right = root.right;
        if(right!=null){
            getTreeList(right, result);
        }
        return result;
    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 226
     *  递归。从根节点开始，临时变量，左右互换；非空节点都如此操作
     *  考虑root==null的情况
     */
    public TreeNode invertTree(TreeNode root) {
        //Check if the root is null
        if(root==null){
            return root;
        }
        //Invert the left subtree
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        //Recursively call the invertTree method on the left and right subtrees
        invertTree(root.left);
        invertTree(root.right);
        //Return the root of the inverted tree
        return root;
    }

    /**
     * 121
     *  max(0, num[j]-nums[i])，i<j；
     *  遍历。购入价格变动时，清空销售价格；价格大于购入价，销售价取最大值
     *      buy=prices[0], sale=0;
     *      prices[i]<buy, max=sale-buy, buy=prices[i], sale=0
     *      prices[i]>buy && prices[i]>sale, sale=prices[i]
     */
    public int maxProfit(int[] prices) {
        if (prices.length <2) {
            return 0;
        }
        int max=0, buy=prices[0], sale=0;
        for (int i =1; i < prices.length; i++) {
            if(prices[i]<buy){
                max=Math.max(max, sale-buy);
                buy=prices[i];
                sale=0;
            }else if(prices[i]>buy && prices[i]>sale){
                sale=prices[i];
            }
        }

        return Math.max(max, sale-buy);

    }

    /**
     * 124
     *  最大路径和
     *  树问题；自顶向下，or自底向上递归；按初始值来选择方向
     *  从单一节点开始，推导多节点情况
     *  节点最大贡献=max(0, val)，0为不经过节点
     *      叶节点val为节点值
     *      非叶节点为(节点val+max(0, 子节点val))
     *  节点最大路径=val+max(0,left.val)+max(0,right.val)
     *
     */
    Integer maxPathVal = Integer.MIN_VALUE;// 避免节点全负
    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxPathVal;
    }

    // 返回的是经过节点最大贡献值，非节点最大路径
    private int maxGain(TreeNode node){
        if(node==null){
            return 0;
        }
        final int leftPathVal = Math.max(0, maxGain(node.left));
        final int rightPathVal = Math.max(0, maxGain(node.right));
        int nodeMaxPathVal = node.val+leftPathVal+rightPathVal;

        maxPathVal = Math.max(maxPathVal, nodeMaxPathVal);
        return node.val+Math.max(leftPathVal,rightPathVal);
    }

    /**   
     * 130
     * dfs，深度优先遍历；临时标记非包围O
     *
     */       
    public void solve(char[][] board) {
        if(board==null || board.length==0 || board[0].length==0){
            return ;
        }
        for (int i =0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if(board[i][j]=='O'){
                    if(i==0 || i==board.length-1
                            || j==0 || j==board[0].length-1
                            || board[i-1][j]=='O' || board[i][j-1]=='O'){
                        board[i][j]='T';
                    }
                }
            }
        }
        for (int i =board.length-1; i >=0; i--) {
            for (int j = board[0].length-1; j >=0; j--) {
                if(board[i][j]=='O'){
                    if(i==0 || i==board.length-1
                            || j==0 || j==board[0].length-1
                            || board[i+1][j]=='O' || board[i][j+1]=='O'
                            || board[i+1][j]=='T' || board[i][j+1]=='T'){
                        board[i][j]='T';
                    }
                }
            }
        }
        for (int i =0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if(board[i][j]=='O'){
                    board[i][j]='X';
                }else if(board[i][j]=='T'){
                    board[i][j]='O';
                }
            }
        }
    }

    /**
     * 402
     * 从左至右，抽取length-k位，组成最小的数字
     * 检索0的个数，看是否会有全0
     * 从最后一个0，开始前导补齐位数
     * map存储
     * 移除0，转为非0数字序列
     *
     * 先朝单调递增序列优化，再移除最后一位
     *  前N位转为有序
     */
    public String removeKdigits(String num, int k) {
        LinkedList<Character> list = new LinkedList<>();
        final int length = num.length();
        final char[] chars = num.toCharArray();
        list.addLast(chars[0]);
        int i;
        for (i=1; i < length; i++) {
            final char aChar = chars[i];
            while(k>0 && !list.isEmpty() && aChar<list.getLast()){
                k--;
                list.removeLast();
            }
            list.addLast(aChar);
            if(k==0){
                i++;
                break;
            }
        }
        for (int j =0; j < k; j++) {
            list.removeLast();
        }
        while(!list.isEmpty() && '0'==list.getFirst()){
            list.removeFirst();
        }
        String result = list.stream().map(e->e.toString()).collect(Collectors.joining(""))
                +num.substring(i);
        result = result.replaceAll("^0+", "");
        return result.length()==0?"0":result;
    }

    // 非3、2；可能性较多，不考虑
    public int move(int distance, int a, int b){
        int steps = distance/a;
        int left = distance%a;
        while(left!=0){
            if(left%b==0){
                steps = Math.abs(steps)+left/b;
                break;
            }
            steps--;
            left += a;
        }
        return steps;
    }


}
